/**
 * @a https://leetcode.cn/problems/find-pivot-index/
 */
#include "common.h"

// 前缀和
class Solution
{
public:
    int pivotIndex(vector<int> &nums)
    {
        unsigned sz = nums.size();
        vector<int> dp(sz + 1);

        dp[0] = nums[0];
        for (int i = 1; i < sz; ++i)
            dp[i] = dp[i - 1] + nums[i];
        int pivot = -1;
        for (int i = 0; i < sz; ++i)
        {
            if (dp[i] - nums[i] == dp[sz - 1] - dp[i])
            {
                pivot = i;
                break;
            }
        }
        return pivot;
    }
};

// 前后缀和
class Solution
{
public:
    int pivotIndex(vector<int> &nums)
    {
        int pivot = -1, sz = nums.size();
        vector<int> prefix_sum(sz);
        vector<int> surfix_sum(sz);
        prefix_sum[0] = 0;
        surfix_sum[sz - 1] = 0;
        for (int i = 1; i < sz; ++i)
        {
            prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1];
            surfix_sum[sz - 1 - i] = surfix_sum[sz - i] + nums[sz - i];
        }
        for (int tmp = 0; tmp < sz; ++tmp)
            if (prefix_sum[tmp] == surfix_sum[tmp])
            {
                pivot = tmp;
                break;
            }
        return pivot;
    }
};
